home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / LANG / GOFER / scripts / Partitions < prev    next >
Text File  |  1993-11-25  |  2KB  |  49 lines
  1. -- Partitions                                        GCW 10/10/92
  2.  
  3. -- represented as lists of integers with entries in decreasing order.
  4.  
  5. type Partition = [Int]
  6.  
  7. -- type declarations for values in this script.
  8. parts   :: Int -> [Partition]
  9. partsTo :: Int -> Int -> [Partition]
  10. dual    :: Partition -> Partition
  11. tableau :: Partition -> String
  12.  
  13. -- the list of partitions of n
  14. parts n = partsTo n n
  15.  
  16. -- partsTo n k gives list of partitions of k into pieces of size <= n.
  17. partsTo 0 _  = [[]]        -- only the empty list
  18. partsTo _ 0  = [[]]        -- only the empty list
  19. partsTo n k  = [ m:ns | m <- reverse [1..min n k], ns <- partsTo m (k-m) ]
  20.  
  21. -- NB. reverse reverses lists, min a b gives minimum of a and b.
  22. -- _ is 'wildcard', i.e. anything.
  23.  
  24. -- the dual of a partition is got by interchanging rows and
  25. -- columns of its Young's tableau.
  26. dual []  = []
  27. dual xs  = (length xs):dual [ x-1 | x <- xs, x > 1 ]
  28.  
  29. length :: [a] -> Int
  30. length x = sum [ 1 | _ <- x ]
  31.  
  32. -- Young's tableau of partition p
  33. tableau p = '\n':concat [ linesOfSize x | x <- reverse (dual p) ]
  34.                where linesOfSize m = (concat (take m stars))++"\n"
  35.                      stars = " *":stars
  36.  
  37. concat :: [[a]] -> [a]
  38. concat []     = []
  39. concat (x:xs) = x ++ concat xs
  40.  
  41. reverse = f [] where
  42.    f xs []     = xs
  43.    f xs (y:ys) = f (y:xs) ys
  44.  
  45. -- NB. concat concatenates a list of lists, take m gives first m items,
  46. -- ++ concatenates two lists, : conses an item to a list, "\n" is string
  47. -- consisting of a single newline, '\n' is newline character.
  48.  
  49.